#pragma once
#include <vector>

void CountSort1(std::vector<int>& arr)
{
	int min_value = arr[0];
	int max_value = arr[0];
	for (auto num : arr)
	{
		if (num < min_value)
			min_value = num;
		if (num > max_value)
			max_value = num;
	}
	int count = max_value - min_value + 1;

	std::vector<int> hash(count, 0);
	for (auto num : arr)
		hash[num - min_value]++;

	int j = 0;
	for (int i = 0; i < count; i++)
		while (hash[i]--)
			arr[j++] = i + min_value;
}
#include <map>
void CountSort(std::vector<int>& arr)
{
	std::map<int, int> mp;
	for (auto num : arr)
		mp[num]++;
	int k = 0;
	for (auto& pair : mp)
	{
		int first = pair.first;
		int second = pair.second;
		while (second--)
			arr[k++] = first;
	}
}